package com.cdream.basic.algorithm.leetcode.slideWindow;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author cdream
 * @date 5/20/21
 */
public class Question438 {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int m = s.length();
        int n = p.length();
        if (m < n) {
            return res;
        }
        int[] i1 = new int[26];
        int[] i2 = new int[26];
        for (int i = 0; i < n; i++) {
            i1[p.charAt(i) - 'a']++;
            i2[s.charAt(i) - 'a']++;
        }
        if (Arrays.equals(i1, i2)) {
            res.add(0);
        }
        for (int i = n; i < m; i++) {
            i2[s.charAt(i) - 'a']++;
            i2[s.charAt(i - n) - 'a']--;
            if (Arrays.equals(i1, i2)) {
                res.add(i - n + 1);
            }
        }
        return res;
    }

}
